package 大按钮;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 5010, n, idx;
    static int[][] son = new int[N][2];
    static boolean[] is_end = new boolean[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int cases = 1; cases <= T; cases++) {
            for (int i = 0; i < N; i++) {
                Arrays.fill(son[i], 0);
            }
            Arrays.fill(is_end, false);
            idx = 0;
            n = in.nextInt();
            int p = in.nextInt();
            for (int i = 0; i < p; i++) {
                String str = in.next();
                insert(str);
            }
            System.out.printf("Case #%d: %d\n", cases, (1L << n) - dfs(0, 0));
        }
    }

    private static long dfs(int p, int s) {
        if (is_end[p]) {
            return 1L << (n - s);
        }
        long res = 0;
        for (int i = 0; i < 2; i++) {
            if (son[p][i] != 0) {
                res += dfs(son[p][i], s + 1);
            }
        }
        return res;
    }

    private static void insert(String str) {
        int p = 0;
        for (int i = 0; i < str.length(); i++) {
            int u = str.charAt(i) == 'B' ? 0 : 1;
            if (son[p][u] == 0) {
                son[p][u] = ++idx;
            }
            p = son[p][u];
        }
        is_end[p] = true;
    }
}
